{ "cells": [ { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "# Problem definition\n", "4 Trucks are available to deliver gas to 5 gas stations. \n", "Each truck has a different capacity and if the company decides to use it to supply to any gas stations, the cost can be modeled by a constant operating cost. The capacity and daily operating costs of each truck are shown in the table below.\n", "\n", "| | Capacity (Liters) | Daily Operating Costs |\n", "|---------|-------------------|-----------------------|\n", "| Truck 1 | 4000 | 45 |\n", "| Truck 2 | 5000 | 50 |\n", "| Truck 3 | 6000 | 55 |\n", "| Truck 4 | 11000 | 60 |\n", "\n", "Each gas station can be supplied only by one truck, but a track may deliver to more than one gas station. The daily demands of each gas station are shown in the table below.\n", "\n", "| | Daily Demand (liters) |\n", "|-----------|-----------------------|\n", "| Station 1 | 1000 |\n", "| Station 2 | 2000 |\n", "| Station 3 | 3000 |\n", "| Station 4 | 5000 |\n", "| Station 5 | 8000 |\n", "\n", "Formulate an Integer Program Problem that can be used to minimise the distribution costs of the logistics operations needed to satisfy the demand of the five stations.\n", "\n", "\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Model definition\n", "### Indexes\n", "- i: Gas stations\n", "- j: Trucks\n", "\n", "### Decision Variables\n", "- Yj (Binary): Truck j is used\n", "- Xij (Binary): Truck j delivers to gas station i\n", "\n", "\n", "\n", "### Objective Function\n", "Minimise cost:\n", "\n", "$\\min z = \\sum{Y_j·Co_j}$\n", "\n", "Where $Co_j$ is the fixed operational cost of using truck j.\n", "\n", "\n", "### Constraints\n", "\n", "\n", "**Single source delivery constraint**\n", "\n", "First, we need to consider the single source constraint, to make sure that only 1 truck delivers to a gas station: \n", "\n", "$\\sum_{j}{X_{ij}}=1 \\quad \\forall i$ \n", "\n", "\n", "**Demand constraint**\n", "\n", "However, we also need to into account the **demand**, to make sure that we satisfy the daily demand in each gas station:\n", "\n", "$\\sum_{j}{d_i*X_{ij}}=d_i \\quad \\forall i$\n", "\n", "Note that these two constraints (single source delivery constraint and demand constraint) are **equivalent**. We can just use the former in our model.\n", "\n", "\n", "**Capacity constraint**\n", "\n", "We also need to take into account the **capacity constraint** to make sure that the amount delivered from any truck is lower than its capacity:\n", "\n", "$\\sum_{i}{d_i*X_{ij}} \\leq c_j \\quad \\forall j$\n", "\n", "**Logical constraint**\n", "\n", "We need to introduce a logical constraint as well, to make sure that the binary decision variables are consistent with each other. Basically, we need to ensure that we only use one truck (i.e. $Y_j=1$) when it delivers to any gas station (i.e. any $X_{ij}$ = 1 for the same j):\n", "\n", "$X_{ij} \\leq Y_j \\quad \\forall i, \\forall j$ \n", "\n", "Another way to express the logical constraint is: \n", "\n", "$\\sum_{i}{X_ij} \\leq M*Y_j \\quad \\forall i, \\forall j$\n", "\n", "Where M is a very large number. In this form, basically what we say is that if a truck is not used (i.e. $Y_j=0$), then the sum of the gas stations it delivers to must be 0. Otherwise, if it is used (i.e. $Y_j=0$), the sum has to be lower than a very large number M. \n", "\n", "Note that, we can also merge this logical constraint with the capacity constraint to yield: \n", "\n", "$\\sum_{i}{d_i*X_ij} \\leq c_jY_j \\quad \\forall j$\n", "\n", "In this form, the right hand side of the logical constraint is modified to take into account the quantity that each truck delivers when it is used, and the right hand side is modified to take into account the maximum capacity of the truck, when it is used. \n", "\n", "With this, our model can be written as: \n", "\n", "$\\min z = \\sum{Y_j·Co_j}$\n", "\n", "$s.t.$ \n", "\n", "$\\sum_{j}{d_i*X_{ij}}=d_i \\quad \\forall i$\n", "\n", "$\\sum_{i}{d_i*X_ij} \\leq c_jY_j \\quad \\forall j$\n", "\n", "## Solution in Python\n", "### Requirements\n", "Run the following script to install the required packages" ] }, { "cell_type": "code", "execution_count": null, "outputs": [], "source": [ "!pip install pulp\n", "!pip install pandas" ], "metadata": { "collapsed": false } }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Optimal\n", "155.0\n" ] } ], "source": [ "import pulp\n", "import pandas as pd\n", "#And we will use numpy to perform array operations\n", "import numpy as np\n", "#We will use display and Markdown to format the output of code cells as Markdown\n", "from IPython.display import display, Markdown\n", "\n", "trucks = [1, 2, 3, 4]\n", "stations = [1, 2, 3, 4, 5]\n", "\n", "capacities = [4000, 5000, 6000, 11000]\n", "\n", "costs = [45, 50, 55, 60]\n", "\n", "demands = [1000, 2000, 3000, 5000, 8000]\n", "\n", "# Instantiate model\n", "model = pulp.LpProblem(\"Truck Deliveries\", pulp.LpMinimize)\n", "\n", "x_vars = pulp.LpVariable.dicts(\"X\",\n", " [(i, j) for i in stations for j in trucks],\n", " lowBound=0,\n", " cat='Binary')\n", "\n", "y_vars = pulp.LpVariable.dicts(\"Y\",\n", " [j for j in trucks],\n", " lowBound=0,\n", " cat='Binary')\n", "\n", "model += (\n", " pulp.lpSum([\n", " costs[j] * y_vars[trucks[j]]\n", " for j in range(len(trucks))])\n", " ), \"Fixed operating costs\"\n", "\n", "# Demand\n", "for i in range(len(stations)):\n", " model += pulp.lpSum([\n", " demands[i]*x_vars[(stations[i], trucks[j])]\n", " for j in range(len(trucks))]) == demands[i], \"station_\" + str(stations[i])\n", " \n", "# Capacity constraints\n", "for j in range(len(trucks)):\n", " model += pulp.lpSum([\n", " demands[i]*x_vars[(stations[i], trucks[j])]\n", " for i in range(len(stations))]) <= capacities[j]*y_vars[trucks[j]], \"truck_\" + str(trucks[j])\n", "\n", "# Solve our problem\n", "model.solve()\n", "print(pulp.LpStatus[model.status])\n", "\n", "# Solution\n", "max_z = pulp.value(model.objective)\n", "print(max_z)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
VariablesSolution
1Y_11.0
2Y_21.0
3Y_30.0
4Y_41.0
\n", "
" ], "text/plain": [ " Variables Solution\n", "1 Y_1 1.0\n", "2 Y_2 1.0\n", "3 Y_3 0.0\n", "4 Y_4 1.0" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
Solution
Trucks1234
Stations
11.00.00.00.0
20.00.00.01.0
31.00.00.00.0
40.01.00.00.0
50.00.00.01.0
\n", "
" ], "text/plain": [ " Solution \n", "Trucks 1 2 3 4\n", "Stations \n", "1 1.0 0.0 0.0 0.0\n", "2 0.0 0.0 0.0 1.0\n", "3 1.0 0.0 0.0 0.0\n", "4 0.0 1.0 0.0 0.0\n", "5 0.0 0.0 0.0 1.0" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "var_Y_df = pd.DataFrame.from_dict(y_vars, orient=\"index\",\n", " columns = [\"Variables\"], dtype=object)\n", "\n", "var_Y_df[\"Solution\"] = var_Y_df[\"Variables\"].apply(lambda item: item.varValue)\n", "display(var_Y_df)\n", "\n", "var_X_df = pd.DataFrame.from_dict(x_vars, orient=\"index\", \n", " columns = [\"Variables\"], dtype=object)\n", "var_X_df[\"Solution\"] = var_X_df[\"Variables\"].apply(lambda item: item.varValue)\n", "index = pd.MultiIndex.from_product([stations, trucks], names=['Stations', 'Trucks'])\n", "var_df2 = pd.DataFrame(var_X_df[\"Solution\"], index=index, columns = [\"Solution\"])\n", "display(var_df2.unstack())" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.4" }, "pycharm": { "stem_cell": { "cell_type": "raw", "source": [], "metadata": { "collapsed": false } } } }, "nbformat": 4, "nbformat_minor": 1 }